/*
 * @Author: your name
 * @Date: 2024-03-21 19:23:12
 * @LastEditTime: 2024-03-21 21:09:27
 * @LastEditors: Please set LastEditors
 * @Description: In User Settings Edit
 * @FilePath: \.leetcode\34.在排序数组中查找元素的第一个和最后一个位置.cpp
 */
/*
 * @lc app=leetcode.cn id=34 lang=cpp
 *
 * [34] 在排序数组中查找元素的第一个和最后一个位置
 */

// @lc code=start
class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        int left  = 0, right = nums.size()-1;
        int start_index = -1, end_index = -1;
        while(left <= right){
            int mid  = left + (right-left)/2;
            if(nums[mid] > target-1){
                right  = mid - 1;
            }
            else{
                left = mid + 1;
            }
            cout<<"start:"<<mid<<endl;
        }
        start_index = left;
        cout<<"start_index:"<<start_index<<endl;
        if(start_index == nums.size() || nums[start_index] != target){
            return {-1,-1};
        }
        left = 0;
        right = nums.size()-1;
        while(left <= right){
            int mid  = left + (right-left)/2;
            if(nums[mid] < target+1){
                left = mid + 1;
            }
            else{
                right  = mid - 1;
            }
            cout<<"end:"<<mid<<endl;
        }
        end_index = right;
        cout<<"end_index:"<<end_index<<endl;
        if(end_index == -1 || nums[start_index] != target){
            return {-1,-1};
        }
        return {start_index,end_index};


    }
};
// @lc code=end

// 思想就是2次二分查找，第一次找插入target小1的数的位置在哪（无论原数组存不存在），
// 第二次找插入target大1的数的位置在哪